Every private-key encryption scheme (yes, even perfectly secret ones) can be broken in the sense that you can find whether a ciphertext
def BruteForce(ciphertext, plaintext1, plaintext2):
for key in [0..2^n - 1]:
if Enc(key, plaintext1) == ciphertext:
return plaintext1
if Enc(key, plaintext2) == ciphertext:
return plaintext2
The reason we are not really worried about this attack, which works for every cipher, is that it runs in exponential time - the for
loop will execute for
loop needs to execute on average to crack a given ciphertext gets larger and it does so very fast. In essence, this is a strategy which always works but is very slow. A key length of just 256 bits means that the algorithm will need to run
According to Wikipedia, the most powerful supercomputer currently in existence is [Frontier](https://en.wikipedia.org/wiki/Frontier_(supercomputer)). It has $606\,208$ AMD Epyc cores running at 2 GHz each and $8\,335\,360$ AMD Radeon Instinct cores which we will also assume to be running at 2 GHz each. This gives us a total of $\,8\,941\,568$ cores all executing $2\times 10^9$ cycles per second which amounts to
$$8\,941\,568 \times 2\times 10^9 = 1.79\times 10^{16} \text{ cycles/s}$$
If we assume that every cycle corresponds to a single key tried (a pretty generous assumption, mind you), then on average this computer would need $\frac{2^{128.5}}{1.79\times 10^{16}} = 2.69 \times 10^{22}$ seconds to crack a ciphertext encrypted with a 256-bit key. This amounts to $8.53 \times 10^{14}$ years which is approximately $62\,263$ times the current age of the Universe. Yes, a *very long time*, indeed.
Therefore, we know that the problem of cracking a ciphertext encrypted with a given
However, it can be shown that if any NP problem can be shown to have an algorithm which executes much faster (i.e. in polynomial time) and is thus a P problem, then all NP problems can be solved much faster. This is called the
If the brute force attack could be optimised to run in $n^{10}$ steps, then it would take only $1.21 \times 10^{24}$ steps to crack a 256-bit key. This can be done on the Frontier supercomputer in a little over 2 years which is *not* infeasible and can be momentous for military purposes, for example.